#include <iostream>
#include "SearchTestHelper.h"


/**
 * 二分查找
 *
 *  对有序数组arr进行查找key
 *  如果找到返回可以的索引
 *  如果未找到返回-1，标识没找到
 *
 * @tparam T
 * @param arr
 * @param n
 * @param key
 */
template<typename T>
T binarySearch(T arr[], int n, T key) {

    //arr[l,r]进行查找key
    int l = 0, r = n - 1;

    while (l <= r) {

        int mid = l + (r - l) / 2;

        if (arr[mid] == key) {      //mid 索引位置的元素就是key 直接返回
            return mid;
        }

        if (key < arr[mid]) {   //查找arr[l,mid-1]

            r = mid - 1;
        } else {     //查找arr[mid+1,r]

            l = mid + 1;
        }
    }
    return -1;

}


int main() {

    int n = 10;
    int rangeL = 0;
    int rangeR = n;
    int swapTime = 0;

    int *arr = generateNearlyRandomArray(n, rangeL, rangeR, swapTime);
    printArray(arr,n);

    cout << binarySearch(arr, n, 5);


    //释放空间，避免内存泄漏
    delete[] arr;
    return 0;
}